import heapq
T = int(input())


def minist(nt,work,num,k):
    result = 0
    count = 0
    people = []
    heapq.heapify(people)
    for i in range(nt):
        count += num[i] //3
    if count < k: return -1
    for i in range(nt):  # 先把凑不齐3人的加上
        if num[i] < 3:
            result += num[i]
        else:
            result += 2
            heapq.heappush(people,-num[i]+2)

    c = 0
    while c<k-1:
        if not people:
            break  # 如果堆为空，退出循环
        top_elem = -heapq.heappop(people)
        if top_elem ==2:
            top_elem -= 2
            c += 1
            result += 2
        elif top_elem==1:
            top_elem -= 1
            c += 1
            result += 1
        while top_elem >= 3 and c<k-1:
            top_elem -= 3
            c += 1
            result += 3
        heapq.heappush(people,top_elem)
    return result+1

for cccccc in range(T):
    teams_num,k = map(int,input().split())  # 表示小队的数量和要组成小队的数量
    work = []
    num = []  # 分别为职业和对应小队的数量
    for _ in range(teams_num):
        a,b = map(int,input().split())
        work.append(a)
        num.append(b)
    r = minist(teams_num,work,num,k)
    print(r)
